
/**
 * @author VernHe
 * @date 2021年05月08日 16:35
 */
public class Solution_021 {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode newList = new ListNode();

        ListNode p = l1;
        ListNode q = l2;
        ListNode node = newList;
        while (p != null && q != null) {
            if (p.val <= q.val) {
                node.next = p;
                p = p.next;
            } else {
                node.next = q;
                q = q.next;
            }
            node = node.next;
        }
        // p 或者 q 为null
        while (p != null) {
            node.next = p;
            node = node.next;
            p = p.next;
        }
        while (q != null) {
            node.next = q;
            node = node.next;
            q = q.next;
        }
        newList = newList.next;
        return newList;
    }
}
